<head>
    <meta charset="UTF-8">
<title>算法提高 Raising the Roof</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】</p>
<p>&nbsp;</p>
<p>你需要帮助一个修屋顶工人估算装修屋顶所需要的材料数量，以保护屋顶的表面不被阳光晒伤。所需要的材根据从正上方俯瞰说能看到的屋顶的面积计算。</p>
<p>屋顶的几何形状是由围住屋顶平面的三角形的顶点开确定的。一个顶点坐标的X和Y是由屋顶的俯瞰图确定的，而Z坐标是这个顶点高于地面的高度，假设地面时平坦的。例如，端点在(10,10,10)和(10,20,10)的线段与地面平行，该线段的长度是10个长度单位。端点在（10,10,10)和(10,18,16)的线段从地面上10个高度单位斜向上16个高度单位；从高处俯瞰它是8个长度单位，但实际是10个长度单位。</p>
<p>在一个屋顶的俯瞰图里，一个较高区域有时候会遮挡一个比较低的区域。只有俯瞰直接可见的屋顶部分才会计入总的面积。例如，假设你俯瞰一幢两层的建筑物，第二层比第一层小，显然，第二层的屋顶面积要计入总面积，而第一层屋顶的可视面积不包括位于第二层正下方被遮挡的部分。</p>
<p>【输入格式】</p>
<p>输入包括若干组描述屋顶的测试用例。每组测试用例的第一行给出整数V（1&lt;=V&lt;=300)和T(1&lt;=T&lt;=1000)，分别表示顶点的数量和三角形的数量；接下来V行</p>
<p>每行是一个顶点的坐标x,y,z；然后分别给出T个三角形的描述，每个三角形给出3个顶点的标号，表示一个屋顶三角形的3个顶点。顶点按照输入中出现的顺序，从1开始编号。</p>
<p>所有坐标都是不大于1的正整数。三角形不会出现3点一线的情况，并且任意两个三角形的部分是独立的，也就是说，这些三角形可能会邻接，但不会重叠或相交。</p>
<p>最后以两个0作为输入结束。</p>
<p>【输出格式】</p>
<p>&nbsp;</p>
<p>&nbsp;</p>
<p>对每一个数据，输出一行，先是数据组号，然后是可见区域，每个组输出后面有一个空行。（详见样例，最后有空行）<br />
【样例输入】</p>
<p>&nbsp;</p>
<p>6 2&nbsp;</p>
<p>10 10 10&nbsp;</p>
<p>10 20 10&nbsp;</p>
<p>20 10 10&nbsp;</p>
<p>10 10 20&nbsp;</p>
<p>10 20 20</p>
<p>20 20 20</p>
<p>1 2 3&nbsp;</p>
<p>4 5 6&nbsp;</p>
<p>3 1&nbsp;</p>
<p>10 10 10</p>
<p>10 18 16&nbsp;</p>
<p>20 10 10&nbsp;</p>
<p>1 2 3&nbsp;</p>
<p>0 0</p>
<div>&nbsp;</div>
<p>&nbsp;</p>
<p>【样例输出】</p>
<p>&nbsp;Case 1: 75.00</p>
<p>&nbsp;</p>
<p>Case 2: 50.00</p>
<p>&nbsp;</p>
<pre><br /></pre>
<p>&nbsp;</p>